// https://www.lintcode.com/problem/merge-two-sorted-interval-lists/

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param list1: one of the given list
     * @param list2: another list
     * @return: the new sorted list of interval
     */
    public List<Interval> mergeTwoInterval(List<Interval> list1, List<Interval> list2) {
        // write your code here
        List<Interval> ret = new ArrayList<>();
        List<Interval> list = new ArrayList<>();
        fillList(list, list1);
        fillList(list, list2);
        Collections.sort(list, new IntervalComparator());
        for (int i = 0; i < list.size(); ++i) {
            Interval in = list.get(i);
            if (ret.size() == 0) {
                ret.add(in);
            } else {
                Interval last = ret.get(ret.size() - 1);
                if ((in.start >= last.start) && (in.start <= last.end)) {
                    last.end = Math.max(in.end, last.end);
                } else {
                    ret.add(in);
                }
            }
        }
        return ret;
    }
    
    public void fillList(List<Interval> target, List<Interval> src) {
        for (int i = 0; i < src.size(); ++i) {
            target.add(src.get(i));
        }
    }
    
    class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval i1, Interval i2) {
            if (i1.start < i2.start) {
                return -1;
            } else if (i1.start > i2.start) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}